package 二叉树练习题;

/**
 * 二元查找树的特点：对于任意一个结点，
 * 它的左子树上所有结点的值都小于这个结点的值，
 * 它的右子树上所有结点的值都大于这个结点的值。
 * 根据这个特点及二元查找树后序遍历的特点可以看出，
 * 这个序列的最后一个元素一定是树的根结点（上图中的结点4），
 * 然后在数组中找到第一个大于根结点4的值5，
 * 那么结点5之前的序列（1,3,2）对应的结点一定位于结点4的左子树上，
 * 结点5（包含这个结点）后面的序列一定位于结点4的右子树上（也就是说，结点5后面的所有值都应该大于或等于4）。
 * 对于结点4的左子树遍历的序列{1,3,2}，以及右子树的遍历序列{5,7,6}可以采用同样的方法来分析，
 * 因此，可以通过递归方法来实现
 */
public class G如何判断一个数组是否是二元查找树后序遍历的序列 {

    public static boolean isAfterOrder(int[] arr, int start, int end) {
        if (arr == null) {
            return false;
        }
        int root = arr[end];
        int i, j;
        //找到第一个大于root的值，那么前面所有的节点都位于root的左子树
        for (i = start; i < end; i++) {
            if (arr[i] > root) {
                break;
            }
        }
        //如果序列是后续遍历的序列，那么从i开始的所有值都应该大于根节点root的值
        for (j = i; j < end; j++) {
            if (arr[j] < root) {
                return false;
            }
        }
        boolean left_isAfterOrder = true;
        boolean right_isAfterOrder = true;
        //判断小于root值的序列是否是一二元查找的后续遍历
        if (j < end) {
            right_isAfterOrder = isAfterOrder(arr, i, end);
        }
        return (left_isAfterOrder && right_isAfterOrder);
    }

    public static void main(String[] args) {
        int arr[] = {1, 3, 2, 5, 7, 6, 4};
        boolean result = isAfterOrder(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        if (result) {
            System.out.println("是");
        } else {
            System.out.println("不是");
        }
    }
}
